package com.hyper_yang.algorithmRecord;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Stack;

// 去除重复字母（结果要求字典序最小）
public class LeetCode_316 {
    // 方法一: 暴力法，贪心策略
    public static String removeDuplicateLetters1(String s) {
        if (s.length() == 0) return "";
        int pos = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) < s.charAt(pos)) {
                boolean isReplaceable = true;
                for (int j = pos; j < i; j++) {
                    boolean isDuplcated = false;
                    // 遍历 i后面的所有字母，看 j位置的字母是否重复出现
                    for (int k = i + 1; k < s.length(); k++) {
                        if (s.charAt(k) == s.charAt(j)) {
                            isDuplcated = true;
                            break;
                        }
                    }
                    // 字母不重复出现，不能替换当前 pos
                    if (!isDuplcated) {
                        isReplaceable = false;
                        break;
                    }
                }
                if (isReplaceable) pos = i;
            }
        }
        // 遍历结束，pos位置的字母就是结果中最左侧的元素
        return s.charAt(pos) + removeDuplicateLetters1(s.substring(pos + 1).replaceAll(s.charAt(pos) + "", ""));
    }

    // 方法二: 贪心策略改进
    public static String removeDuplicateLetters2(String s) {
        if (s.length() == 0) return "";
        int pos = 0;

        int[] count = new int[26];
        for (int i = 0; i < s.length(); i++)
            count[s.charAt(i) - 'a']++;

        // 遍历字符串，找到当前最左端字母
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) < s.charAt(pos)) pos = i;
            if (--count[s.charAt(i) - 'a'] == 0) break;
        }
        return s.charAt(pos) + removeDuplicateLetters2(s.substring(pos + 1).replaceAll(s.charAt(pos) + "", ""));
    }

    // 方法三: 使用栈
    public static String removeDuplicateLetters(String s) {
        // 保存去重后的结果
        Stack<Character> stack = new Stack<>();
        // 快速判断字符是否在栈中出现
        HashSet<Character> seenSet = new HashSet<>();
        // 快速判断字母出现的最后位置
        HashMap<Character, Integer> lastSeen = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            lastSeen.put(s.charAt(i), i);
        }
        // 判断字符是否需要入栈
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            // c没出现果，才考虑入栈
            if (!seenSet.contains(c)) {
                // c 入栈之前，要判断之前栈顶元素是否会在后面重复出现
                while (!stack.isEmpty() && c < stack.peek() && lastSeen.get(stack.peek()) > i)
                    seenSet.remove(stack.pop());
                stack.push(c);
                seenSet.add(c);
            }
        }
        StringBuilder str = new StringBuilder();
        for (Character c : stack)
            str.append(c.charValue());
        return str.toString();
    }

    public static void main(String[] args) {
        System.out.println(removeDuplicateLetters("bcabc"));
        System.out.println(removeDuplicateLetters("cbacdcbc"));
    }
}
